package com.zengqingfa.algorithm.cz.chapter03;

import java.util.Iterator;

/**
 * @author zengqingfa
 * @className LinkList
 * @description
 * @create 2021/8/31 12:44
 */
public class TwoWayList<T> implements Iterable<T> {

    //首节点
    private Node head;
    private Node tail;
    //链表的长度
    private int size;

    public TwoWayList() {
        head = new Node(null, null, null);
        tail = null;
        size = 0;
    }

    //清空链表
    public void clear() {
        tail = null;
        head.next = tail;
        head.pre = head;
        size = 0;
    }

    //获取链表的长度
    public int length() {
        return size;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获取指定索引处的元素
     * 通过for循环来获取
     *
     * @param index
     * @return
     */
    public T get1(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("参数非法");
        }
        Node node = head.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.item;
    }


    /**
     * 获取指定索引处的元素
     * 通过while循环来获取
     *
     * @param index
     * @return
     */
    public T get2(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("参数非法");
        }
        Node node = head;
        int start = 0;
        while (node.next != null) {
            node = node.next;
            if (start == index) {
                break;
            }
            start++;
        }
        return node.item;
    }

    /**
     * 向链表中添加元素
     *
     * @param item
     */
    public void insert(T item) {
        Node newNode = new Node(head, item, null);
        if (tail == null) {
            head.next = newNode;
        } else {
            Node oldTail = tail;
            oldTail.next = newNode;
        }
        tail = newNode;
        size++;
    }

    /**
     * 向指定位置处插入元素
     *
     * @param item
     * @param index
     */
    public void insert(T item, int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("位置非法");
        }
        //获取到位置index之前的节点
        Node pre = head;
        for (int i = 0; i < index; i++) {
            pre = head.next;
        }
        //当前节点
        Node curr = pre.next;
        Node newNode = new Node(pre, item, curr);
        if (curr != null) {
            curr.pre = newNode;
        }
        pre.next = newNode;
        size++;
    }

    /**
     * 删除指定位置处的元素
     *
     * @param index
     * @return
     */
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("位置非法");
        }
        //获取删除索引处前一个位置的元素
        Node pre = head;
        for (int i = 0; i < index; i++) {
            pre = head.next;
        }
        //删除的当前元素
        Node curr = pre.next;
        Node next = curr.next;
        pre.next = next;
        next.pre = pre;
        size--;
        return curr.item;
    }

    //获取第一个元素
    public T getFirst() {
        if (isEmpty()) {
            return null;
        }
        return head.next.item;
    }

    //获取最后一个元素
    public T getLast() {
        if (isEmpty()) {
            return null;
        }
        return tail.item;
    }

    /**
     * 查找元素在链表中第一次出现的位置
     *
     * @param item
     * @return
     */
    public int indexOf(T item) {
        Node node = head;
        int index = 0;
        while (node.next != null) {
            if (node.next.item.equals(item)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    @Override
    public Iterator iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator {

        private Node n;

        public LIterator() {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }

    private class Node {
        Node pre;
        T item;
        Node next;


        public Node(Node pre, T item, Node next) {
            this.pre = pre;
            this.item = item;
            this.next = next;
        }
    }
}